package DataStrucures;

public class BalanceBinaryTreeDemo {
    public static void main(String[] args) {
        int[]arr={10,12,8,9,7,6};
        AvlTree avlTree=new AvlTree();
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new AvlNode(arr[i]));
        }
        avlTree.infixOrder();
        System.out.println(avlTree.getRoot().height());
        System.out.println(avlTree.getRoot().leftHeight());
        System.out.println(avlTree.getRoot().rightHeight());
    }
}
class AvlTree{
    private AvlNode root;

    public AvlNode getRoot() {
        return root;
    }

    public void add(AvlNode node){
        if(root==null){
            root=node;
        }else {
            root.add(node);
        }
    }
    public void infixOrder(){
        if(root==null){
            System.out.println("空树");
        }else {
            root.infixOrder();
        }
    }
}
class AvlNode{
    int value;
    AvlNode left;
    AvlNode right;

    @Override
    public String toString() {
        return "AvlNode{" +
                "value=" + value +
                '}';
    }

    public AvlNode(int value) {
        this.value = value;
    }

    public int leftHeight(){
        if(left==null){
            return 0;
        }
        return left.leftHeight()+1;
    }
    public int rightHeight(){
        if(right==null){
            return 0;
        }
        return right.rightHeight()+1;
    }
    public int height(){
        return Math.max(left==null?0: left.height(), right==null?0: right.height())+1;
    }
    private void leftRotate(){//左旋转创建一个新的节点并将当前节点的左右关系进行赋值再将新头节点的值赋值给当前的头节点最后通过改变左右指向将现值的原节点去掉
        AvlNode avlNode=new AvlNode(value);
        avlNode.left=left;
        avlNode.right=right.left;
        value=right.value;
        right=right.right;
        left=avlNode;
    }
    private void rightRotate(){//同上
        AvlNode avlNode=new AvlNode(value);
        avlNode.right=right;
        avlNode.left=left.right;
        value=left.value;
        left=left.left;
        right=avlNode;
    }
    public void add(AvlNode node){//比本节点小放左边反之放右边
        if(node==null){
            return;
        }
        if(node.value<this.value){
            if(this.left!=null){
                this.left.add(node);
            }
            if(this.left==null){
                this.left=node;
            }
        }else {
            if(this.right!=null){
                this.right.add(node);
            }
            if(this.right==null){
                this.right=node;
            }

        }
        if(this.rightHeight()-this.leftHeight()>1){//右边高度大于左边时左旋转

            leftRotate();
        }
        if(this.leftHeight()-this.rightHeight()>1){//左边高度大于右边时右旋转
            rightRotate();
        }
    }
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }
}